#pragma once

namespace wjb
{
	template<class K, class V>
	struct bstnode
	{
		bstnode(const K& key, const V& val)
			:_key(key)
			, _val(val)
			, _left(nullptr)
			, _right(nullptr)
		{}

		bstnode* _left;
		bstnode* _right;
		K _key;
		V _val;

	};

	template<class K, class V>
	class bstree
	{
		typedef bstnode<K, V> node;
	public:
		bstree()
		{}

		bool insertR(const K& key, const V& val)
		{
			return _insertR(_root, key, val);
		}

		bool eraseR(const K& key)
		{
			
			return _eraseR(_root, key);
		}

		node* findR(const K& key)
		{
			return(_root, key);
		}

		void inorder()
		{
			_inorder(_root);
		}

	private:


		bool _insertR(node*& root, const K& key, const V& val)
		{
			if (root == nullptr)
			{
				root = new node(key, val);
				return true;
			}

			if (root->_key < key)
				return _insertR(root->_right, key, val);
			else if (root->_key > key)
				return _insertR(root->_left, key, val);
			else
				return false;

		}

		bool _eraseR(node*& root, const K& key)
		{
			if (root == nullptr)
				return false;

			if (root->_key < key)
				return _eraseR(root->_right, key);

			else if (root->_key > key)
				return _eraseR(root->_left, key);

			else
			{
				node* del = root;
				if (root->_left == nullptr)
				{
					root = root->_right;
				}

				else if (root->_right == nullptr)
				{
					root = root->_left;
				}

				else
				{
					node* leftmax = root->_left;
					while (leftmax)
					{
						leftmax = leftmax->_right;
					}
					swap(root->_key, leftmax->_key);

					return _eraseR(root->_left, key);
				}
				delete del;
				return true;
			}

		}

		node* _findR(node* root, const K& key)
		{
			if (root == nullptr)
				return nullptr;

			if (root->_key < key)
				return _findR(root->_right, key);

			else if (root->_key > key)
				return _findR(root->_left, key);

			else
				return root;
		}



		void _inorder(node* root)
		{
			if (root == nullptr)
			{
				return;
			}

			_inorder(root->_left);
			cout << root->_key << " : " << root->_val << endl;
			_inorder(root->_right);

		}
		node* _root;
	};
}
